package com.example.lcpractice.heading_offer;

import com.example.lcpractice.datastructure.ListNode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
 * <p>
 * 示例1：
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 * 限制：
 * <p>
 * 0 <= 链表长度 <= 1000
 *
 * @author hd
 * @date 2022/7/13 14:34
 */
public class q13 {

    public static void main(String[] args) {
        ListNode singleLinkedList = ListNode.getSingleLinkedList();

        ListNode singleLinkedList2 = ListNode.getSingleLinkedList2();
        System.out.println(mergeTwoLists(null, null));
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ArrayList<ListNode> listNodes = new ArrayList<>();

        while (l1 != null || l2 != null) {
            if (l1 == null) {
                listNodes.add(l2);
                l2 = l2.next;
                continue;
            }
            if (l2 == null) {
                listNodes.add(l1);
                l1 = l1.next;
                continue;
            }

            if (l1.val >= l2.val) {
                listNodes.add(l2);
                l2 = l2.next;
            } else {
                listNodes.add(l1);
                l1 = l1.next;
            }
        }
        if (listNodes.size() > 0) {
            ListNode head = listNodes.get(0);
            ListNode temp = head;
            for (int i = 1; i < listNodes.size(); i++) {
                temp.next = listNodes.get(i);
                temp = temp.next;
            }
            return head;
        }
        return null;
    }

    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        // 头指针 val为空始终指着真正头部
        ListNode headNullPointer = new ListNode();
        // 指定链表末尾
        ListNode cur = headNullPointer;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                // 直接指针入栈
                cur.next = l1;
                l1 = l1.next;
            } else {
                // 直接指针入栈
                cur.next = l2;
                l2 = l2.next;
            }
            // 当前指针指着末尾（因为入栈一个节点）
            cur = cur.next;
        }
        // 结束循环，或者压根没进入循环，必有一空，
        // 若进入循环则有一个链表可能剩余不为空（本身升序），连上去即可
        // 若没进入循环至少一个为空，则连上去不为空处
        cur.next = l1 != null ? l1 : l2;
        return headNullPointer.next;
    }
}
